package com.itheima.datastructure.linkedlist;

//判断回文链表
public class E09Leetcode234 {
    /*
    1.找中间点
    2.中间的后的半个节点反转
    3.原链表与反转后的链表比较
     */
    public boolean isPalindrome1(ListNode head) {
        ListNode p1= head;
        ListNode p2= head;
        while(p2!=null && p2.next!=null){
            p1=p1.next;
            p2=p2.next.next;
        }
        ListNode middle = p1;
        ListNode n1=null;
        while(middle !=null){
            ListNode o2= middle.next;
            middle.next=n1;
            n1= middle;
            middle =o2;
        }
        ListNode newHead= n1;
        while(newHead !=null){
            if(newHead.val!= head.val){
                return false;
            }
            newHead=newHead.next;
            head=head.next;
        }
        return true;
    }

    public boolean isPalindrome(ListNode head){
        ListNode p1= head;//慢
        ListNode p2= head;//快
        ListNode n1=null;//新头
        ListNode o1=head;//旧头
        while(p2!=null && p2.next!=null){
            p1=p1.next;
            p2=p2.next.next;

            //反转链表
            //ListNode o2=o1.next;
            o1.next=n1;
            n1=o1;
            //o1=o2;
            o1=p1;
        }
        System.out.println(n1);
        System.out.println(p1);

        if(p2!=null){//奇数节点
            p1=p1.next;
        }
        while(n1!=null){
            if(n1.val!= p1.val){
                return false;
            }
            n1=n1.next;
            p1=p1.next;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new E09Leetcode234().isPalindrome(ListNode.of(1,2,2,1)));
        System.out.println(new E09Leetcode234().isPalindrome(ListNode.of(1,2,3,2,1)));
    }
}
